'''
牛客网
BM4 合并两个排序的链表
'''

class ListNode:
    def __init__(self,val,next = None):
        self.val = val
        self.next = next

class solution:
    def Merge(self,pHead1:ListNode,pHead2:ListNode)->ListNode:
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1

        head  = ListNode(0)
        cur = head

        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next

        if pHead1:
            cur.next = pHead1
        else:
            cur.next = pHead2

        return head.next

def printListNode(node:ListNode):
    while node:
        print(node.val,end="->"if node.next else "\n")
        node = node.next


if __name__ == "__main__":
    phead1 = ListNode(1,ListNode(3,ListNode(5,ListNode(10,ListNode(18)))))
    phead2 = ListNode(2,ListNode(3,ListNode(7,ListNode(8,ListNode(9)))))

    solution = solution()
    result = solution.Merge(phead1,phead2)
    printListNode(result)